package com.it.od.od2024.od20240306;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author: liminghui
 * @date: 2024/3/5 23:53
 * @version: 1.0
 * @description: 跳格子2
 * 小明和朋友玩跳格子游戏， 有 n 个连续格子组成的圆圈，每个格子有不同的分数，
 * 小朋友可以选择从任意格子起跳，但是不能跳连续的格子，不能回头跳，也不能超过一圈 ;
 * 给定一个代表每个格子得分的非负整数数组，计算能够得到的最高分数。
 * 给定一个数例，第一个格子和最后一个格子收尾相连，如：2 3 2
 * 输出能够得到的最高分，如：3
 * 用例1
 * 输入
 * 2 3 2
 * 输出
 * 3
 * 用例2
 * 输入:
 * 1 2 3 1
 * 输出
 * 4
 * 用例3：
 * 94 40 49 65 10
 * 输出
 * 159
 * 关键递推公式：
 * dp[i]=max(dp[i-1],dp[i-2]+arr[i])
 */
public class Main3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int jump = jump(arr);
        System.out.println(jump);

    }

    private static int jump(int[] nums) {
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int dp1 = jumpRange(nums, 0, nums.length - 2);
        int dp2 = jumpRange(nums, 1, nums.length - 1);
        return Math.max(dp1, dp2);
    }

    private static int jumpRange(int[] nums, int start, int end) {
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }

}
